This invention relates to a media access control mechanism for packet transmission over a buffer insertion ring and, in particular, to an algorithm for ensuring local fairness in transmission resource sharing in a buffer insertion ring.
Access control in a buffer insertion ring is designed for asynchronous transmission of variable size packets. A node in a buffer insertion ring can transmit a packet as long as its insertion buffer is empty. A packet arriving from an upstream ring access point (AP) is given non-preemptive priority over frames to be added at a downstream AP on a buffer insertion ring. In other words, ring traffic has preemptive priority over node traffic that is to be transmitted on the ring. If a downstream AP is in the process of adding a packet to the ring when a packet arrives from an upstream AP, then the upstream AP""s packet is buffered temporarily. When the end of the added packet is transmitted, it is immediately followed by the buffered packet. The buffer insertion scheme can, however, result in a phenomenon known as a xe2x80x9cstarvation.xe2x80x9d An AP suffers from starvation when an upstream AP transmits continuously and blocks a downstream AP from access to the ring. When this occurs, the downstream AP is said to be xe2x80x9ccoveredxe2x80x9d by upstream ring traffic sources. The prevention of starvation in a buffer insertion ring requires a media access fairness mechanism to regulate access to the ring. An optimal solution quickly achieves fairness among traffic sources, and maximizes network throughput while maintaining a minimal ring access delay and contributing minimally to operating overhead.
Several fairness algorithms have been developed for controlling traffic in a buffer insertion ring. One such algorithm is the xe2x80x9cSATxe2x80x9d algorithm described by Cidon in an article entitled xe2x80x9cMetaRing a full-duplex ring with fairness and spatial reusexe2x80x9d, IEEE Transactions on Communications, Vol. 41, No. 1, January 1993, pp. 110-120. The algorithm regulates access to the ring by use of a control signal called, an SAT that circulates in a direction opposite to the data traffic. Each AP in the ring is assigned a fixed transmit quota. The AP forwards the SAT upstream without delay unless it has been unable to satisfy its quota. The SAT is held by the AP until it has satisfied its quota, after which it will forward the SAT upstream. This algorithm suffers from the drawbacks associated with token control in a ring topology. Namely, the algorithm impacts throughput if a small quota allocation is selected. The algorithm also results in degraded access delay if nodes are granted large quotas. The algorithm likewise causes unnecessary losses of throughput in asymmetrically loaded rings.
Another algorithm referred to as the xe2x80x9cFULLxe2x80x9d algorithm is described by Saito et al in an article entitled xe2x80x9cQOS Guarantees for high-speed variable-length packet LANsxe2x80x9d available on the web site: www.sail.t.u-tokyo.ac.jp/pisai/research. The FULL algorithm is an enhancement to the SAT algorithm. The enhancement is enabled by assuming that the ring access logic implements a shortest path forwarding policy. Given such a policy, more than one SAT token is simultaneously applied on each half of the ring. The FULL algorithm provides a marginal improvement of about 10% on the performance of the original SAT algorithm but shares its drawbacks noted above.
Another algorithm developed for access control on buffer insertion rings is the REQ/GNT algorithm described in an article by Chen et al entitled xe2x80x9cA local fairness algorithm for Gigabit LANs/MANs with spatial reusexe2x80x9d, IEEE Journal on Selected Areas in Communications, Vol. 11, No. 8, October 1993, pp. 1183-1192. In accordance with the REQ/GNT algorithm, each AP operates in two modes: restricted and non-restricted mode. In restricted mode, a node can transmit only a predefined quota of data units. In non-restricted mode, the AP has free access to the ring yielding non-preemptive priority to the upstream traffic. A starved node triggers the fairness mechanism by sending a request message (REQ) upstream. On receipt of such a message, the upstream AP enters a restricted mode. If an AP that receives the REQ message cannot provide silence because it is receiving traffic from upstream sources, it will in turn forward the REQ message upstream. A node in restricted mode is permitted to add a fix quota of traffic to the ring. Once this quota is achieved, the node must cease transmission. After all upstream APs have transmitted their quota, the starved AP has a transmit opportunity. After the starved AP has transmitted its quota of traffic, it releases the upstream nodes from the restricted state by issuing a GNT message. Upon receiving a GNT message, the upstream AP follows similar rules. The upstream AP will in turn forward a GNT message upon satisfaction of its quota. The REQ/GNT algorithm offers better performance than the SAT and FULL algorithms and achieves more optimal throughput in asymmetrically loaded rings. However, the REQ/GNT algorithm falls short of the optimal throughput for certain traffic patterns and suffers from high head of line ring delay.
Each of the above-described algorithms suffers from shortcomings that are well known and acknowledged by their inventors. Specifically, the algorithms throttle throughput and contribute to head of line delay (HOL). HOL delay is defined as the amount of time a first packet in the add buffer of a node has to wait before it is inserted into the ring. Consequently, bandwidth utilization is not optimally achieved using these algorithms. One contributory factor is that high throughput and short HOL delay are often conflicting objectives.
There therefore exists a need for a fairness algorithm that provides both short HOL delay and high bandwidth utilization. There also exists a need for an algorithm that rapidly converges to a fair rate, is simple to implement, and readily scales with growth in ring topology.
It is therefore an object of the invention to provide a method of media access control for packet transmission over a buffer insertion ring which overcomes the disadvantages of prior art algorithms.
It is a further object of the invention to provide an adaptive rate control (ARC) algorithm that operates on the basis of rate calculations performed at each node in the ring.
It is a further object of the invention to provide an ARC algorithm that performs rate calculations using information available at each node as well as information received from a downstream link partner node.
It is yet a further object of the invention to provide a media access control algorithm in which each node computes its own local fair add rate as well as a rate which the node deems to be a fair add rate for its upstream link partner.
It is yet a further object of the invention to provide a media access control algorithm for packet transmission over a buffer insertion ring which runs continuously on the ring to regulate each node""s access to the ring.
It is yet another object of the invention to provide an algorithm for media access control for packet transmission over a buffer insertion ring which contributes little to the operating overhead of the ring.
These and other objects of the invention are realized in a method of media access control for packet transmission over a buffer insertion ring, comprising steps performed by each node in the buffer insertion ring of:
computing at regular intervals a local packet add rate and an advertised packet add rate for an upstream link partner node;
communicating the advertised add rate to the upstream link partner node; and
adding packets to the ring at a rate that does not exceed the local packet add rate until a new add rate is computed.
In accordance with a further aspect of the invention, there is provided a method of media access control for packet transmission over a buffer insertion ring in which a packet arriving from an upstream node in the ring is given non-preemptive priority over packets to be added to the ring, the method ensuring fair transfer resource sharing, comprising steps performed by each node in the buffer insertion ring of:
computing at regular intervals T a local packet add rate using the formula:
Add_Rate(nT)=(Add_Rate(nTxe2x88x92T)+DS_Rate(nT))/2
wherein:
Add_Rate(nTxe2x88x92T) is the add rate of an immediately preceding interval T; and
DS_Rate is an advertised rate of a downstream link neighbor node;
also computing at each interval nT an add rate for an upstream link partner node using the formula:
IF (Tandem_Rate(nT) is 0)
Advertised_Rate(nT)=1
ELSE
Advertised_Rate(nT)=Min(1xe2x88x92Tandem_Rate(nT)*(1xe2x88x92EMPT), DS_Rate(nT))
END IF
wherein:
Tandem_Rate is a number of bytes passing through a tandem buffer of the node, normalized to a link rate of the upstream link, during an interval TSTAT, Txe2x89xa6TSTAT;
EMPT is a Boolean that indicates whether the node has any packets to send on the ring; and
DS_Rate is the advertised rate of a downstream link neighbor node;
communicating the advertised add rate to the upstream link partner node; and
adding packets to the ring at a rate that does not exceed the local packet add rate until a next local packet add rate is computed.
The ARC algorithm operates on the basis of rate calculations that are performed at each node. The rate calculations are performed using rate information available at each node as well as rate information received at the node from a downstream link partner. The rate information available at each node is the rate at which packets are received in the insertion buffer, known as the tandem traffic rate. The information received from the downstream link partner relates to a rate which the downstream link partner deems to be a fair add rate for the node. This is referred to as the advertised rate. The tandem traffic rate and the advertised rate are used to compute a local fair add rate. Each node uses its add rate as the fair add rate until the algorithm dictates that it perform a new rate calculation. The node can add traffic during an interval between add rate calculations only up to the maximum allowed by the calculated add rate. Once the node has achieved its add rate quota, the node is not permitted to add more traffic to the ring until after a next add rate calculation.
Each node communicates the advertised rate it calculates to its upstream link partner. The upstream link partner node, upon receipt of the advertised rate, uses it in the calculations of its own add rate as well as a new advertised rate that it transmits to its own upstream link partner node. This process continuously runs on the ring, constantly regulating each node""s access to the ring. Simulation results have confirmed that the ARC fairness algorithm adjusts the add rate of each node to a fair value. The adjustment is rapidly achieved even under a heavy traffic load in which each node transmits at its full rate to its further downstream node.